There has been explosive growth in Internet traffic due to the increased number of Internet users, various service demands from those users, the implementation of new services, such as voice-over-IP (VOIP) or streaming applications, and the development of mobile Internet. Conventional routers, which act as relaying nodes connected to sub-networks or other routers, have accomplished their roles well, in situations in which the time required to process packets, determine their destinations, and forward the packets to the destinations is usually smaller than the transmission time on network paths. More recently, however, the packet transmission capabilities of high-bandwidth network paths and the increases in Internet traffic have combined to outpace the processing capacities of conventional routers.
This has led to the development of massively parallel, distributed architecture routers. A distributed architecture router typically comprises a large number of routing nodes that are coupled to each other via a plurality of switch fabric modules and an optional crossbar switch. Each routing node has its own routing (or forwarding) table for forwarding data packets via other routing nodes to a destination address.
Traditionally, a single processor is used to forward all packets in a router or switch. Even in routers with multiple forwarding table lookup threads, these threads are under control of a single processor and use a single forwarding table. Thus, conventional routers retain route information in a central location and do not distribute route information within the router. Also, since many prior art routers do not have multiple routing nodes, these routers do not experience the problems that arise when a distributed architecture combines routing nodes with small table space with more powerful routing nodes in a large route capacity router.
The main disadvantage of prior art routers is the inability to handle line rate forwarding for high bandwidth links, such as 10 Gbps interfaces. This is especially true for the longest prefix matches encountered when forwarding IPv6 packets. Also, when the table space limitations of current routers are exceeded, the routers drop routes from their routing tables or cease to learn new routes. Thus, conventional routers drop packets that would be routable if adequate table space were available. Conventional routers may use a default route instead of dropping a packet. But there is only one default route for the whole router, so the chances of successfully routing the packet are small. If no default route is defined, conventional routers drop the packets.
The applicants and the assignee of the present application have filed patent applications disclosing a number of solutions to the problems associated with prior art routers. These patent applications include 1) U.S. patent application Ser. No. 10/431,770, entitled “Apparatus and Method for Combining Forwarding Tables in a Distributed Architecture Router”, filed on May 8, 2003; 2) U.S. patent application Ser. No. 10/655,192, entitled “Apparatus and Method for Classifying Traffic in a Distributed Architecture Router”, filed on Sep. 4, 2003; 3) U.S. patent application Ser. No. 10/658,977, entitled “Apparatus and Method for Performing High-Speed Lookups in a Routing Table”, filed on Sep. 10, 2003; 4) U.S. patent application Ser. No. 10/794,506, entitled “Apparatus and Method for Forwarding Mixed Data Packet Types in a High-Speed Router”, filed on Mar. 5, 2004; and 5) U.S. patent application Ser. No. 10/832,010, entitled “Apparatus and Method for Route Summarization and Distribution in a Massively Parallel Router”, filed on Apr. 26, 2004. The disclosures and teachings of U.S. patent application Ser. Nos. 10/431,770, 10/655,192, 10/658,977, 10/794,506, and 10/832,010 are hereby incorporated by reference into the present disclosure as if fully set forth herein.
Each of these previously filed applications solves some of the problems of large forwarding table indices and large numbers of routes. U.S. patent application Ser. Nos. 10/431,770 and 10/655,192 provide optimal solutions for line rates up to at least 1 Gbps. U.S. patent application Ser. Nos. 10/658,977 and 10/794,506 provide two different solutions for line rates up to at least 10 Gbps. U.S. patent application Ser. No. 10/658,977 provides a pipelined approach and U.S. patent application Ser. No. 10/794,506 provides a parallel processing approach. Finally, U.S. patent application Ser. No. 10/832,010 provides a technique for reducing the number of routes through route summarization and using default routes to implement an “always route” approach.
However, the routers described in U.S. patent application Ser. Nos. 10/431,770, 10/655,192, 10/658,977, 10/794,506, and 10/832,010 implement trie tree search tables in which each stage of the trie tree consumes one nibble (i.e., 4 bits) of the subnet mask. This is unnecessarily limiting. It is desirable to use subnet masks of arbitrary lengths, rather than using only masks that are integer multiples of four bits.
Also, the route summarization techniques disclosed in U.S. patent application Ser. No. 10/832,010 use default routes to support an “always route” technique, wherein data traffic packets associated with an unknown route are forwarded along a known route having a similar prefix (i.e., a prefix matching in as many most significant bits as possible). That technique assumed that other routers along the known route may have more information about the unknown route since these other routers already know a similar route. However, conventional techniques for distributing the known and unknown routes to trie tree search tables are slow and require the use of many processing resources.
Therefore, there is a need in the art for improved high-speed routers. In particular, there is a need for a high-speed router that implements a trie tree search table that can be searched using subnet masks that do not lie on nibble boundaries. There is a further need for an improved technique for flooding a trie tree search table with default route information.